package Aula14;

public class TestaArvoreBinariaImpl implements TestaArvoreBinaria{

	public int altura(No raiz) {
		if(raiz == null){
			return 0;
		}
		if(!raiz.hasLeft() && !raiz.hasRight()){
			return 0;
		}
		return 1 + altura(raiz.getLeft()) + altura(raiz.getRight());
	}
	
	public boolean ehBinariaCompleta(No raiz) {
		if(!ehEstritamenteBinaria(raiz))
			return false;
		int profundidadeLeft = profundidade(raiz);
		int profundidadeRight = profundidade(raiz);
		No folhaLeft = raiz;
		No folhaRight = raiz;
		
		while(folhaLeft.hasLeft()){
			folhaLeft = folhaLeft.getLeft();
			profundidadeLeft++;
		}
		
		while(folhaRight.hasRight()){
			folhaRight = folhaRight.getRight();
			profundidadeRight++;
		}
		return profundidadeLeft == profundidadeRight;
	}

	public boolean ehBinariaDePesquisa(No raiz) {
		if (raiz.hasLeft()) {
			if (raiz.getLeft().getKey() > raiz.getKey())
				return false;
		}
		
		if (raiz.hasRight()) {
			if (raiz.getKey() > raiz.getRight().getKey()) {
				return false;
			}
		}
		if(raiz.hasLeft() && raiz.hasRight()) {
			return ehBinariaDePesquisa(raiz.getLeft())
				&& ehBinariaDePesquisa(raiz.getRight());
		}
		return true;
	}

	public boolean ehEstritamenteBinaria(No raiz) {
		if(!raiz.hasLeft() && !raiz.hasRight()){
			return true;
		} else {
			if (raiz.hasLeft() && raiz.hasRight()) {
				return ehEstritamenteBinaria(raiz.getLeft())
						&& ehEstritamenteBinaria(raiz.getRight());
			} else {
				return false;
			}
		}
	}

	public int profundidade(No n) {
		if(n == null){
			return 0;
		}
		No pai = n.getParent();
		int cont = 0;
		while(pai != null){
			pai = pai.getParent();
			cont++;
		}
		return cont;
	}
	
}
